'''
Created on 05/01/2011

@author: Josafat Guerrero josafatisai@gmail.com

'''

import math

from Face import Face
from Vertex import Vertex
from HalfEdge import HalfEdge
from shapely.coords import CoordinateSequence
from spyderlib.widgets.editortools import EdgeLine



#-- OGR 
try:
    from osgeo import ogr
except ImportError:
    import ogr
#-- Shapely
from shapely.wkt import loads
from shapely.geometry import LineString



class DCEL:
    '''
    classdocs
    '''

   

    def convert(self, polygons):
    
        ##start storing the faces
        ## indexes to start enumerating everything


        #we require a world face
        outerFace = Face('z', None, None)            
        self.faces['z'] = outerFace;
        
        lastVertex = None#used for computing edges
        currentVertex = None
        #Basically, all the polygons id start at 1,    
        for p in polygons:
#            print "-------------------------------------------------------------"
#            print "Appending things at Face " + str(self.faceId)
            currentFace = Face(str(self.faceId), None, None)
            self.faces[str(self.faceId)] = currentFace;
            self.faceId += 1;#not gonna use this anymore until next face
        
            coordinates = list(p['geom'].exterior.coords)# is a coordinate sequence
            #print "Coordinates for " + currentFace.toString() +  ":" 
            #print coordinates# printing as a list                        
            
            #############################################

            ##  checking the first vertex
            
            tmpVertexCoords = coordinates.pop(0)#TOOK OUT THE FIRST VERTEX
            if str(tmpVertexCoords) in self.verticesIdx: ## if the vertex exists, just retrieve info
                lastVertex = self.verticesIdx[str(tmpVertexCoords)]#retrieve the vertex
            else:
                ###print "ADD Vertex: " + str(self.vertexIndex)# the current vertex idx 
                tmpVertex = Vertex(str(self.vertexIndex), tmpVertexCoords, None)# storing self.vertexIndex +=1;
                self.verticesIdx[str(tmpVertexCoords)] = tmpVertex
                self.vertices[str(self.vertexIndex)] = tmpVertex
                self.vertexIndex += 1;
                lastVertex = tmpVertex

            
            #now we start with the remaining objects

            
            ## 
            edgesList = [];# this list is used to fill the remaining objects as next, prev, inner object, outerobject
            #edgesListTwin =[]
            ########################################## start processing the rest of the coordinates
            #note all coordinates are defined clockwise
            for i in xrange(len(coordinates)):
                coordsi = coordinates[i]# para cada par coordenado
                coordsKey = str(coordsi)
                
                #si el vertice ya existe , 
                if coordsKey in self.verticesIdx:
                    ###print "RR   Repeated Vertex: " + self.verticesIdx[coordsKey].id + " " + coordsKey    
                    tmpVertex = self.verticesIdx[coordsKey]
                    currentVertex = tmpVertex
                                    
                else:# add a new vertex to the list
                    ###print "ADD Vertex: " + str(self.vertexIndex)# the current vertex idx
                    tmpVertex = Vertex(str(self.vertexIndex), coordsi, None) # storing currentself.vertexIndex +=1;
                    self.verticesIdx[coordsKey] = tmpVertex
                    self.vertices[str(self.vertexIndex)] = tmpVertex #just copy the reference
                    self.vertexIndex += 1;
                    currentVertex = tmpVertex
                    
                


                next = None
                prev = None

                #An edge can always be created as 2 vertices always exists

                edgeKey = lastVertex.getId() + "_" + currentVertex.getId();
                edgeKeyTwin = currentVertex.getId() + "_" + lastVertex.getId();
                
                #########################################################################################
                #if the edge doesnt exists, add it to the idx and also its twin  
#                print "ckecking " + edgeKey 
                if edgeKey not in self.halfEdgesIdx: ## edge v1v2 is different than v2v1
                    #if is not in the index, add it

                    name1 = "E_" + str(self.edgeIndex) + "_1" # I use this names E_1_1, E_1_2
                    name2 = "E_" + str(self.edgeIndex) + "_2"
                    
                    ###print "ADD  Edge " + name1 + " Origin: " + lastVertex.id  
                    ###print "ADD  Edge " + name2 +" TWIN"  + " Origin: " + currentVertex.id 

                    ##################### lleno la mayoria de la informacion
                    newEdge = HalfEdge(name1 , ##id
                                            lastVertex, # pointer to the origin
                                            None, #twin           
                                            currentFace, #incidentFAce pointer
                                            None, #next
                                            None, #prev
                                            currentVertex
                                            )
                    
                    
                    
                    newEdgeTwin = HalfEdge(name2 ,
                                            currentVertex, #origin
                                            newEdge, #twin pointer 
                                            outerFace, #dont know who is incident to , default outerFace
                                            None, #no next
                                            None, # No prev)
                                            lastVertex
                                            );  
                    
                    newEdge.twin = newEdgeTwin #now i can add the twin
                    
                    self.halfEdgesIdx[edgeKey] = newEdge# indexo por vertice1_vertice2, obtengo EdgeId11
                    self.halfEdgesIdx[edgeKeyTwin ] = newEdgeTwin# indexo por vertice1_vertice2, obtengo  EdgeId12
                    
                    ##
                    self.halfEdges[name1] = self.halfEdgesIdx[edgeKey]
                    self.halfEdges[name2] = self.halfEdgesIdx[edgeKeyTwin ]

                    ####
                    edgesList.append(newEdge); #keep the record for the next pass, to fill next and prev values
                    #edgesListTwin.append(newEdgeTwin);
                    ####
                    
                    #print "ADD  Edge " + newEdge.id + " Origin: " + newEdge.origin.id + " TWIN: " + newEdge.twin.id + " Incident: " + newEdge.incidentFace.id  
                    #print "ADD  Edge " + newEdgeTwin.id + " Origin: " + newEdgeTwin.origin.id + " TWIN: " + newEdgeTwin.twin.id + " Incident: " #+ newEdgeTwin.incidentFace.id  

                    ###print "ADD  Edge " + newEdge.toString();#id + " Origin: " + newEdge.origin.id + " TWIN: " + newEdge.twin.id + " Incident: " + newEdge.incidentFace.id  
                    ###print "ADD  Edge " + newEdgeTwin.toString();#id + " Origin: " + newEdgeTwin.origin.id + " TWIN: " + newEdgeTwin.twin.id + " Incident: " #+ newEdgeTwin.incidentFace.id  

                    lastVertex.incidentEdge = newEdge
                    currentVertex.incidentEdge = newEdgeTwin# addinf incident edge to this vertex
                    self.edgeIndex += 1;
                    ###################
                else:# si si existe la arista
                    #puede ser porque alguien mas la agrego, pero del otro lado, ie, desde el twin
                    #en ese caso le falta el incident face
                    #aun le falta next y prev, pero eso hasta la siguiente pasada
                    #twin debe estar asignado ya 

                    currentEdge = self.halfEdgesIdx[edgeKey]
#                    print "EXisting edge " + currentEdge.toString();
#                    print "UPdating Info ... "
#                    print "   Incident Face: " + currentFace.toString();
#                    print currentEdge.toString();
#                    print "Updated ... "
                    currentEdge.incidentFace = currentFace;
                   
                    edgesList.append(currentEdge);
                    self.halfEdgesIdx[edgeKey] = currentEdge 
                    self.halfEdges[currentEdge.id] = currentEdge; 
#                    print  self.halfEdgesIdx[edgeKey].toString()
                    
                    

                lastVertex = currentVertex#

                    

            ## end of: for coordinates, no more vertexes added, no more edges added
            
            ####################################  a second round to complete all the remaining references  on edged is needed.       
            #completing next and prev references on edges list only on my side
            
          
           
###            print "------------------------------------------- UPDATING EDGES next and prev"
###            for e in edgesList:
###                print e.toString()
###            print "-------------------------------------------- "
            for i in xrange(len(edgesList) - 1):
                ###print i
                edge = edgesList[i]
                #edgeTwin = edgesListTwin[i]
                ###print "Antes " + edge.toString()
                edge.prev = edgesList[i - 1]
                edge.next = edgesList[i + 1]
                
                ### if everything fails remove this comments
                #edge.prev.twin = edgesListTwin[i - 1  ]                
                #edge.next.twin = edgesListTwin[i + 1]
                ###
                
                ###print "Desp " + edge.toString();
             #processing the last element
   
            lastIndex = len(edgesList) - 1
            #print lastIndex
            edge = edgesList[lastIndex]
            ###print "Antes " + edge.toString()
            edge.prev = edgesList[lastIndex - 1]
            edge.next = edgesList[0]
#
            #edge.prev.twin = edgesListTwin[lastIndex -2]               
            #edge.next.twin = edgesListTwin[0]

            
            ###print "Desp " + edge.toString();
            edgesList = []# clear everything
            #print edge.toString();
             #######################3
            ###print "------------------------------------------- ENDOF UPDATING EDGES next and prev"
    
            ### updating this face, adding the first edge
            currentFace.outerComponent = edge.twin; # and outer edge
            #currentFace.innerComponents= edge.twin; # and outer edge
        
        for key in iter(self.halfEdges):
            
            tmpedge = self.halfEdges[key];
            edgekeystart = tmpedge.incidentFace.id + "_" + tmpedge.origin.id
            edgekeyend = tmpedge.incidentFace.id + "_" + tmpedge.end.id

            self.faceStartVertexIdx[edgekeystart ] = tmpedge
            self.faceEndVertexIdx[edgekeyend ] = tmpedge
        
        
        print "Updating f0 edges"
        f0edges = self.findEdgesAtFace(outerFace);# single time operation
        #those edges need to be filled
        for e in f0edges:

            if e.next == None:
                e.next = self.findEdgeAtVertexFace(e.end, e.incidentFace)
                pass;   
                
            if e.prev == None:
                e.prev = self.findEdgeAtEndVertexNFace(e.origin, e.incidentFace);
                pass;
#            print e.toString()
        print "Updated f0 edges"
        #############################
        ###creating indexes
        
        
         
    def __init__(self):
        '''
        Constructor
        '''
        self.faces = {}
        self.verticesIdx = {} # key is a pair of coordinates, value is a Vertex object
        self.vertices = {} # key is vertex id
        self.halfEdges = {} # key is # E_x_y
        self.halfEdgesIdx = {}# key is a pair of vertices, v1_v2, v1 is origin, v2 is end

        self.faceStartVertexIdx = {} #holds a pointer to the edge with such face and such vertex as origin
        self.faceEndVertexIdx = {} #holds a pointer to the edge with such face and such vertex as end

        self.faceId = 0;
        self.vertexIndex = 1;
        self.edgeIndex = 1;
        

     
    def printData(self):
        ''' 
            This method tries to print a nice screen with all the information
        '''
        
        print "****************************************************************"
        print "****************************************************************"
        print "****************************************************************"
        print "VERTICES"
        for v in iter(self.vertices):
            print self.vertices[ v ].toString()
 
        print "****************************************************************"
        print "FACES"
        for f in iter(self.faces):
            print self.faces[f].toString()

        print "****************************************************************"
        print "EDGES"
        for e in iter(self.halfEdges):
            print self.halfEdges[e].toString()
        print "****************************************************************"


    def printLineSegments(self):
        lineSegments = self.findLineSegments();
      
        for lineSegmentKey in iter(lineSegments):
            lineSegment = lineSegments[lineSegmentKey]
            print "Segment: " + lineSegmentKey 
            for s in lineSegment:
                print s.id
            
            conv = self.convertLine2Tuple(lineSegment);
            for c in conv:
                print c
            
    def convertLine2Tuple(self, listOfVertices):
        '''
            This method recieves a single list of vertices (v1,v2,v3,v4, ... vn)
            and returns the corresponding coordinates on a list
            ( )
        '''
        listOfTupleCoordinates = []
        for v in listOfVertices:
            vertex = self.vertices[v.id]
            listOfTupleCoordinates.append(vertex.coords);
        #print listOfTupleCoordinates
        return listOfTupleCoordinates
    
    
     
    def findLineSegments(self):
        '''
        This method is used to extract all the pair of nodes for all the polygons. 
        The pairs are stored on a dictionary as (vi,vj,face_k)
        Is noted that (v1,vj,face_k) == (vj,vi,face_l) , ie, the order of the vertices doesnt matter.
        
        '''
        print "Finding line Segments"
        lineSegments = {};

        counter = self.getGraphArity();# indexed per vertex, arity # ok
            

        # for each face, make a walk and find all the vertexes with more than 2 incident edges, that means a node
        for fkey in iter(self.faces):
            
            if fkey == 'z':
                fkey = '1'
#            print "************************************* Face: -" + fkey + "-"
            localNodeList = [];

            face = self.faces[fkey]

            edgeStart = self.findFirstEdgeAtFace(face)#the first edge depends on the actual order of the keys            

#            print "Walking around " + fkey "looking for a node to start"
            edge = edgeStart;


            if counter[ edge.origin.id ] > 2:
#                print "Found a Node on first vertex: " + edge.origin.id
                #if edge.origin.id == '63225':
                #    print "-************************************"
                localNodeList.append(edge.origin);

            else:# have to first encounter a node
 #               print "Node not found on first vertex: " + edge.origin.id
                edge = edge.next;
                while (counter[ edge.origin.id ] < 3) & (not (edgeStart.origin.id == edge.origin.id)) :
 #                   print "L:ooking for a node on : " + edge.origin.id 
                    edge = edge.next;
 #               print "Stop Counter: " + str(counter[ edge.origin.id ]) + "    VERTICES: " + " = " + edge.origin.id + " = " + edgeStart.origin.id + " EDge:" + edge.id
                localNodeList.append(edge.origin);# on both cases, just add such node as a starting node

            edgeStart = edge
            edge = edge.next;
            
            #now, everythime, i start on a node and i know that such node must end my nodes list
            while not edge.id == edgeStart.id:
  #              print "Walking on EDge " + edge.id
                result = counter[ edge.origin.id ]             
                if result > 2:
 #                   print "Node FOUND   " + edge.origin.id
                    localNodeList.append(edge.origin);
                edge = edge.next
            
            # i will always end with more at least one node            

            localNodeList.append(localNodeList[0]);

  #          print "List of nodes for FAce f " + fkey 
#            for node in localNodeList:
#                print node.toString();
#            
            #########################3
            #no i have to create a set of tuples for the node pairs
            # it should looks like
            # [a,b,c,d,e,f,g,a]
            # so i must find an edge a as vertes and a face f 
            
            
            #print 'Creating the list of segments'    
            segmentCounter = 0
            
            
            #########################3

            #############################
            while (len(localNodeList) > 1):
                #print "Trying  segment " + str(segmentCounter)
                tmpVertexList = []
                
                startNode = localNodeList.pop(0);# a node is a vertex
                endNode = localNodeList[0]

                #print "Start Node: " + startNode.toString()
                #print "End Node: " + endNode.toString()
                

                currentEdge = self.findEdgeAtVertexFace(startNode, face);
                startEdge = currentEdge;            
                
                #tmpVertexList.append(startNode);# a node is a vertex
                
                tmpVertexList.append(currentEdge.origin);#add the id of the vertex
                currentEdge = currentEdge.next
                
                while not currentEdge.origin == endNode:#while we cant find the next node
                    #print " End Node "  + endNode.id +  " not found yet at origin of" + currentEdge.toString()
                    tmpVertexList.append(currentEdge.origin);#add the id of the vertex
                    currentEdge = currentEdge.next

                tmpVertexList.append(endNode);#add the last node vertex
                
#                    print "Trying to add line segment: " 
#                    for  v in tmpVertexList:
#                        print v.toString()
                
                
                ### try to add to the line segment list
                key1 = startNode.id + "_" + endNode.id + "_" + startEdge.id
                key2 = endNode.id + "_" + startNode.id + "_" + currentEdge.prev.twin.id 

                test1 = key1 in  lineSegments;
                test2 = key2 in  lineSegments;

                if not test1 | test2:# if is already included, dont do anything
                    #add to the edges list
#                        print "SEgment added " + key1
                    lineSegments[key1] = tmpVertexList;# this is all that must be done for this line segment
                else:
                    #print "segment not added"
                    pass;
                ###
            ### getting back to face for
            ## getting back to the next face
            
        return lineSegments;

## completely deprecated
    def findLineSegments2(self):
        '''
        This method is used to extract all the pair of nodes for all the polygons. 
        The pairs are stored on a dictionary as (vi,vj,face_k)
        Is noted that (v1,vj,face_k) == (vj,vi,face_l) , ie, the order of the vertices doesnt matter.
        
        '''
        print "Finding line Segments"
        lineSegments = {};

        counter = self.getGraphArity();# indexed per vertex, arity
            
        # for each face, make a walk and find all the vertexes with more than 2 incident edges, that means a node
        for fkey in iter(self.faces):
            
            if fkey == 'z':
                fkey = '1'
            print "************************************* Face: -" + fkey + "-"
            localNodeList = [];

            face = self.faces[fkey]

            edgeStart = self.findFirstEdgeAtFace(face)#the first edge depends on the actual order of the keys            

#            print "Walking around " + fkey
            edge = edgeStart;

            if counter[ edge.origin.id ] > 2:
                #print "Found a Node: " + edge.origin.id
                #if edge.origin.id == '63225':
                #    print "-************************************"
                localNodeList.append(edge.origin);
            edge = edgeStart.next;
            
             ### now start walking around the edges  looking for nodes   
             # the condition is quite weak
            while not edge.id == edgeStart.id:
                #print "Walking on EDge " + edge.id
                result = counter[ edge.origin.id ]             
                if result > 2:
                    #print "Found a Node: " + edge.origin.id
                    localNodeList.append(edge.origin);
                edge = edge.next
            
            #creo que tengo que hacer la ultima verificacion
            
            ################ this code corrects all the incinsistencies on the missing nodes
            ### have several cases
            
            if(len(localNodeList) > 1):#if at least have 2 node
                print "Found at least " + str(len(localNodeList)) + " node"
                localNodeList.append(localNodeList[0]);
            if(len(localNodeList) == 1):#if at least have a node

                localNodeList.append(edgeStart.prev.origin)## otro wuick fix
                print "Found only " + str(len(localNodeList)) + " node. Adding no node"
                pass;
            
            if(len(localNodeList) == 0):# have no node and have to add an artificial one, but this will lead to errors
                print "No nodes found"
                ################### mega fix, solo para islas

                
                localNodeList.append(edgeStart.origin)
                localNodeList.append(edgeStart.prev.origin)## porque me brinque este en las islas
                localNodeList.append(edgeStart.origin)
            #################################
            
#            print "List of nodes for FAce f " + fkey 
#            for node in localNodeList:
#                print node.toString();
#            
            #########################3
            #no i have to create a set of tuples for the node pairs
            # it should looks like
            # [a,b,c,d,e,f,g,a]
            # so i must find an edge a as vertes and a face f 
            
            
            #print 'Creating the list of segments'    
            segmentCounter = 0
            
            
            #########################3
            #need to create an exception if is an isolated polygon
            if (len(localNodeList) == 1):
                
#                print "Island"
                tmpVertexList = []
                startvertex = localNodeList.pop(0)

                currentEdge = self.findEdgeAtVertexFace(startvertex, face);
                
                while not (currentEdge.end == startvertex):
                    #print currentEdge.toString()
                    tmpVertexList.append(currentEdge.origin)
                    currentEdge = currentEdge.next        
                tmpVertexList.append(startvertex);

                print "Trying to add line segment: " 
                for  v in tmpVertexList:
                    print v.toString()
                        
                key1 = startvertex.id + "_" + startvertex.id + "_" + currentEdge.id


                #print key1
             

                test1 = key1 in  lineSegments;
                

                if  not test1 :# if is already included, dont do anything
#                    print "SEgment added " + key1
                    lineSegments[key1] = tmpVertexList;# this is all that must be done for this line segment
                    #print tmpVertexList

            else:
                #############################
                while (len(localNodeList) > 1):
                    #print "Trying  segment " + str(segmentCounter)
                    tmpVertexList = []
                    
                    startNode = localNodeList.pop(0);# a node is a vertex
                    endNode = localNodeList[0]
    
                    #print "Start Node: " + startNode.toString()
                    #print "End Node: " + endNode.toString()
                    
    
                    currentEdge = self.findEdgeAtVertexFace(startNode, face);
                    startEdge = currentEdge;            
                    
                    #tmpVertexList.append(startNode);# a node is a vertex
                    
                    while not currentEdge.origin == endNode:#while we cant find the next node
                        #print " End Node "  + endNode.id +  " not found yet at origin of" + currentEdge.toString()
                        tmpVertexList.append(currentEdge.origin);#add the id of the vertex
                        currentEdge = currentEdge.next
    
                    tmpVertexList.append(endNode);#add the last node vertex
                    
#                    print "Trying to add line segment: " 
#                    for  v in tmpVertexList:
#                        print v.toString()
                    
                    
                    ### try to add to the line segment list
                    key1 = startNode.id + "_" + endNode.id + "_" + startEdge.id
                    key2 = endNode.id + "_" + startNode.id + "_" + currentEdge.prev.twin.id 
    
                    test1 = key1 in  lineSegments;
                    test2 = key2 in  lineSegments;
    
                    if not test1 | test2:# if is already included, dont do anything
                        #add to the edges list
#                        print "SEgment added " + key1
                        lineSegments[key1] = tmpVertexList;# this is all that must be done for this line segment
                    else:
                        #print "segment not added"
                        pass;
                    ###
                ### getting back to face for
                ## getting back to the next face
            
        return lineSegments;


    #needs to be tested
    def replaceLine(self, oldLine, newLine):
        '''
        Each line is a list of tuples
        
         THis code attempts to replace an old line which  the simplified version, or in general , 
         any other line, bigger or smaller.
          A line looks like this:   (v1,v2, .. Vn-1,Vn) , where v1 = n1 and vn = n2, 
          starts on node N1 and ends at N2
                 
         The general procedure when simplifing lines s the following
         
         1.- Drop the unused vertices or add new vertices accordingly.
         
         
         2.-  Keep track of 
              2.1 The edge that has  it origin at N1, and ends at v2
              2.2 its twin
              2.3 edge that has  it origin at N2, and ends at vn-1   
              2.4 its twin
         3.- Keep track of the affected edges in an ordered way and separated on by face
         4.- Create new edges accordingly keeping them in a proper order
         5.- Update the affected vertices with the new edges
         6.- Updated the affected faces with the first edge, and the other face with the twin of the last edge  
        
         
        '''
        
#        print "Replacing Line"
        if (len(oldLine) == len(newLine)):
#            print "Replacing Line ... Nothing done"
            return None; # we still consider only simplification
        
        dropVertices = []
       #checks if a point on the original line is present on the new line
       #if the point is not present, is kept
#        print "Replacing Line..."
        for ov in oldLine: 
#            print ov
            
            for v in newLine:
                #print v;
                if v == ov: # if the new point is contained on old list
                        found = True;
                        
            if not found:
                #print ov
                dropVertices.append(ov);# the missing points are kept, why???
        ###################
        
        ## keep track of the important edges
        
        #find an edge that start on the node and ends on the next vertex of the original line
        #find an edge that start on the last node  and ends on the previous vertex of the original line
        # with this we keep track of the previous edges
        
#        print "-- -- -- "
#        print self.verticesIdx[str(oldLine[0])].id + "_" + str (self.verticesIdx[str(oldLine[0])].coords)
#        print self.verticesIdx[str(oldLine[1])].id + "_" + str(self.verticesIdx[str(oldLine[1])].coords)
#        print self.verticesIdx[str(oldLine[-2])].id + "_" + str(self.verticesIdx[str(oldLine[-2])].coords)
#        print self.verticesIdx[str(oldLine[-1])].id + "_" + str(self.verticesIdx[str(oldLine[-1])].coords)

        firstEdgeKey = self.verticesIdx[str(oldLine[0])].id + "_" + self.verticesIdx[str(oldLine[1])].id
        lastEdgeKey = self.verticesIdx[str(oldLine[-2])].id + "_" + self.verticesIdx[str(oldLine[-1])].id
        
#        print firstEdgeKey
#        print lastEdgeKey

        #old first edges
        firstEdge = self.halfEdgesIdx[firstEdgeKey];
        lastEdge = self.halfEdgesIdx[lastEdgeKey];
        
        #start creating new edges
             
        face1 = firstEdge.incidentFace;
        face2 = firstEdge.twin.incidentFace;
        
        edgesList = [];
        

        # creating new edges with the new vertices   
        for vindex in xrange(len(newLine) - 1):# create new edge and its twin
            vorig = self.verticesIdx[str(newLine[vindex])];
            vend = self.verticesIdx[str(newLine[vindex + 1])];
            
            edgeKey = vorig.id + "_" + vend.id;
            edgeKeyTwin = vend.id + "_" + vorig.id;
                
            #########################################################################################
            #the edge shouldnt exists, as we are droping them

            name1 = "E_" + str(self.edgeIndex) + "_1" # I use this names E_1_1, E_1_2
            name2 = "E_" + str(self.edgeIndex) + "_2"
                    
            ##################### lleno la mayoria de la informacion
            newEdge = HalfEdge(name1 ,
                               vorig, # pointer to the origin
                                None, #twin           
                                face1, # need to find it
                                None, #next
                                None, #prev
                                vend
                            );
                    
            newEdgeTwin = HalfEdge(name2 ,
                                vend, #origin #############################
                                newEdge, #twin pointer 
                                face2, #dont know who is incident to , default outerFace
                                None, #no next
                                None, # No prev)
                                vorig
                                );  
                    
            newEdge.twin = newEdgeTwin #now i can add the twin
            
            ##add to the index the new edges
            
            self.halfEdgesIdx[edgeKey] = newEdge# indexo por vertice1_vertice2, obtengo EdgeId11
            self.halfEdgesIdx[edgeKeyTwin ] = newEdgeTwin# indexo por vertice1_vertice2, obtengo  EdgeId12
                    
            ##
            self.halfEdges[name1] = self.halfEdgesIdx[edgeKey]
            self.halfEdges[name2] = self.halfEdgesIdx[edgeKeyTwin ]

########## indexes
            self.faceStartVertexIdx[ face1.id + "_" + vorig.id ] = newEdge
            self.faceEndVertexIdx[face1.id + "_" + vend.id] = newEdge
            
            self.faceStartVertexIdx[ face2.id + "_" + vend.id ] = newEdgeTwin
            self.faceEndVertexIdx[face2.id + "_" + vorig.id] = newEdgeTwin

### end of indexes

            edgesList.append(newEdge); #keep the record for the next pass, to fill next and prev values
         
            vorig.incidentEdge = newEdge
            #vend.incidentEdge = newEdgeTwin# addinf incident edge to this vertex
            
            face1.outerComponent = newEdge;
            face2.outerComponent = newEdge.twin;

            #print newEdge.toString();
            #print newEdgeTwin.toString();
            
            
            #### creating indexes
            



            
            
            
            self.edgeIndex += 1;
            ###################

        

        #### now need to update the remaining info on such edges, prev and next
        ##### also need to update faces outerComponent and maybe their inner components
        
        ## set the first and last edge
        
        
        
        # first a bulk pointer assignment
        # first and las pointer will be wrong
        for i in xrange(len (edgesList) - 1):
            e = edgesList[i]
            #print e.toString()
            e.prev = edgesList[i - 1]
            e.next = edgesList[i + 1]
        
        
        
        #rewriting things
        edgesList[0].prev = firstEdge.prev
        edgesList[0].twin.next = firstEdge.twin.next# on the twin side
        edgesList[0].prev.next = edgesList[0]
        edgesList[0].twin.next.prev = edgesList[0].twin
        ##ok


        edgesList[-1].next = lastEdge.next
        edgesList[-1].twin.prev = lastEdge.twin.prev
        edgesList[-1].next.prev = edgesList[-1]
        edgesList[-1].twin.prev.next = edgesList[-1].twin
        
        print (len(edgesList))
        if len(edgesList) > 1:
            edgesList[-1].prev = edgesList[-2]
            edgesList[-1].twin.next = edgesList[-2].twin
        
        
        #dropping old edges
        for vindex in xrange(len(oldLine) - 1):# create new edge and its twin
            key = self.verticesIdx[str(oldLine[vindex])].id + "_" + self.verticesIdx[str(oldLine[vindex + 1])].id
            keyTwin = self.verticesIdx[str(oldLine[vindex + 1])].id + "_" + self.verticesIdx[str(oldLine[vindex])].id
            
            
            self.halfEdgesIdx[key] = None
            self.halfEdgesIdx[keyTwin] = None
            del self.halfEdgesIdx[key]
            del self.halfEdgesIdx[keyTwin]            
        
        ##dropping some other indexes
        ## but not today

    def findEdgeAtEndVertexNFace(self, vertex, face):
        return self.faceEndVertexIdx[face.id + "_" + vertex.id]

    def findEdgeAtEndVertexNFace2(self, vertex, face):
                
        edge = None;
        for edgeKey in iter(self.halfEdges):
            tmpEdge = self.halfEdges[edgeKey]
            if (tmpEdge.end.id == vertex.id) & (tmpEdge.incidentFace.id == face.id):
                return tmpEdge;
        return None;
    
    def findEdgeAtStartEndVertexNFace2(self, startVertex, endVertex, face):
                
        edge = None;
        for edgeKey in iter(self.halfEdges):
            tmpEdge = self.halfEdges[edgeKey]
            if (tmpEdge.origin.id == startVertex.id) & (tmpEdge.end.id == endVertex.id) & (tmpEdge.incidentFace.id == face.id):
                return tmpEdge;
        return None;
    
    
    
    def findEdgeAtVertexFace(self, vertex, face):
        #print "Looking: " + face.id + "_" + vertex.id
        return self.faceStartVertexIdx[face.id + "_" + vertex.id]

    def findEdgeAtVertexFace2(self, vertex, face):
        '''
            This operation is time consuming, some improvements are needed
            Right now is a linear search
        '''
        
#        print "Finding edge at Vertex " + vertex.id + " at Face " + face.id        
        edge = None;
        for edgeKey in iter(self.halfEdges):
            tmpEdge = self.halfEdges[edgeKey]
            if (tmpEdge.origin.id == vertex.id) & (tmpEdge.incidentFace.id == face.id):
#                print "Edge Found : "+ tmpEdge.toString()
                return tmpEdge;
            else:
                #print "Not in Edge " + tmpEdge.toString()
                pass; 
                
        return None;
    
    def findFirstEdgeAtFace(self, face):
                
#        print "Finding Edge at face " + face.id 
        for edgeKey in iter(self.halfEdges):
#            print "Trying with edge " + edgeKey
            tmpEdge = self.halfEdges[edgeKey]
            if (tmpEdge.incidentFace.id == face.id):
#                print "Found an edge incident on " + face.id
#                print tmpEdge.toString()
                return tmpEdge;
        return None;
    
    def findEdgesAtFace(self, face):
                
        edges = []
#        print "Finding Edges at face " + face.id 
        for edgeKey in iter(self.halfEdges):
            #print "Trying with edge " + edgeKey
            tmpEdge = self.halfEdges[edgeKey]
            if (tmpEdge.incidentFace.id == face.id):
#                print "Found an edge incident on Face " + face.id
#                print tmpEdge.toString()
                edges.append(tmpEdge);
        return edges;
    
    
    def getVertexArity(self, vertex):
        '''
        Method to compute the actual arity of a vertex.
        Requires a full search, linear search on the edge list.
        For each edge, check if the origin vector is the requested one.
        If so, add one to the counter and also store the edge
        
        '''
        
        print "Cheking Vertex: " + Vertex.id
        incidentEdges = [];
        counter = 0;
        for e in iter(self.halfEdges):
            if e.origin.id == Vertex.id:
                incidentEdges.append(e);
                print e.origin.id;
                counter += 1;
        return counter;
    
    def getGraphArity(self):
        '''
        This method computes the actual arity of each vertex
        '''
        counter = {};
        
        #first set all he keys
        for vkey in iter(self.vertices):
            counter[str(self.vertices[vkey].id)] = 0
            
        for e in iter(self.halfEdges):
            counter[self.halfEdges[e].origin.id] += 1

    #    for c in iter(counter):
     #       print "V " + c + "-  = " + str( counter[c])
        return counter;


    def createPolygons2(self):
       
        '''
        This method is used to extract all the pair of nodes for all the polygons. 
        The pairs are stored on a dictionary as (vi,vj,face_k)
        Is noted that (v1,vj,face_k) == (vj,vi,face_l) , ie, the order of the vertices doesnt matter.
        
        '''
        print "Creating Polygons"
        lineSegments = {};
        polygons = {};


        # just made a simple walk
        for fkey in iter(self.faces):            
            if not fkey == 'z':

                #print "Polygon " + fkey
                vertices = []
                face = self.faces[fkey]
                
                edgeStart = face.outerComponent
                
                #print edgeStart.toString()
                
                vstart = edgeStart.origin
                vend = edgeStart.end
                
                vertices.append(vstart.coords);
                
                edge = self.findEdgeAtVertexFace(vend, face)
                vertex = edge.origin
                
                while not (vstart == vertex):
                ## basicamente voy a buscar la arista que empieza en vstart y termina en vend
                    vertices.append(vertex.coords);
                    edge = self.findEdgeAtVertexFace(edge.end, face)
                    vertex = edge.origin;

                vertices.append(vertex.coords);
                
                polygons[fkey] = vertices;
        

            
        return polygons;
        
    def createPolygons(self):
       
        '''
        This method is used to extract all the pair of nodes for all the polygons. 
        The pairs are stored on a dictionary as (vi,vj,face_k)
        Is noted that (v1,vj,face_k) == (vj,vi,face_l) , ie, the order of the vertices doesnt matter.
        
        '''
        print "Creating Polygons"
        lineSegments = {};
        polygons = {};


        # just made a simple walk
        for fkey in iter(self.faces):            
            if not fkey == 'z':

                #print "Polygon " + fkey
                vertices = []
                face = self.faces[fkey]
                
                edgeStart = face.outerComponent
    
                #print edgeStart.toString()
                vertices.append(edgeStart.origin.coords);
    
                edge = edgeStart
                edge = edge.next         
                #print edge.toString()
                while  (not (edgeStart.origin.id == edge.origin.id)) :
                    #print edge.toString()   
                    #print "Appending vertex " + edge.origin.id
                    #print "Appending vertex " + edge.origin.id
                    vertices.append(edge.origin.coords);
                    edge = edge.next

                # i think I am still missing a last point
             
                vertices.append(edge.origin.coords);## test if is correct
                polygons[fkey] = vertices;
        

            
        return polygons;
        
